// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/control-equivalence.h"
#include "src/compiler/node-properties.h"

#define TRACE(...)                \
    do {                          \
        if (FLAG_trace_turbo_ceq) \
            PrintF(__VA_ARGS__);  \
    } while (false)

namespace v8 {
namespace internal {
    namespace compiler {

        void ControlEquivalence::Run(Node* exit)
        {
            if (!Participates(exit) || GetClass(exit) == kInvalidClass) {
                DetermineParticipation(exit);
                RunUndirectedDFS(exit);
            }
        }

        // static
        STATIC_CONST_MEMBER_DEFINITION const size_t ControlEquivalence::kInvalidClass;

        void ControlEquivalence::VisitPre(Node* node)
        {
            TRACE("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
        }

        void ControlEquivalence::VisitMid(Node* node, DFSDirection direction)
        {
            TRACE("CEQ: Mid-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
            BracketList& blist = GetBracketList(node);

            // Remove brackets pointing to this node [line:19].
            BracketListDelete(blist, node, direction);

            // Potentially introduce artificial dependency from start to end.
            if (blist.empty()) {
                DCHECK_EQ(kInputDirection, direction);
                VisitBackedge(node, graph_->end(), kInputDirection);
            }

            // Potentially start a new equivalence class [line:37].
            BracketListTRACE(blist);
            Bracket* recent = &blist.back();
            if (recent->recent_size != blist.size()) {
                recent->recent_size = blist.size();
                recent->recent_class = NewClassNumber();
            }

            // Assign equivalence class to node.
            SetClass(node, recent->recent_class);
            TRACE("  Assigned class number is %zu\n", GetClass(node));
        }

        void ControlEquivalence::VisitPost(Node* node, Node* parent_node,
            DFSDirection direction)
        {
            TRACE("CEQ: Post-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
            BracketList& blist = GetBracketList(node);

            // Remove brackets pointing to this node [line:19].
            BracketListDelete(blist, node, direction);

            // Propagate bracket list up the DFS tree [line:13].
            if (parent_node != nullptr) {
                BracketList& parent_blist = GetBracketList(parent_node);
                parent_blist.splice(parent_blist.end(), blist);
            }
        }

        void ControlEquivalence::VisitBackedge(Node* from, Node* to,
            DFSDirection direction)
        {
            TRACE("CEQ: Backedge from #%d:%s to #%d:%s\n", from->id(),
                from->op()->mnemonic(), to->id(), to->op()->mnemonic());

            // Push backedge onto the bracket list [line:25].
            Bracket bracket = { direction, kInvalidClass, 0, from, to };
            GetBracketList(from).push_back(bracket);
        }

        void ControlEquivalence::RunUndirectedDFS(Node* exit)
        {
            ZoneStack<DFSStackEntry> stack(zone_);
            DFSPush(stack, exit, nullptr, kInputDirection);
            VisitPre(exit);

            while (!stack.empty()) { // Undirected depth-first backwards traversal.
                DFSStackEntry& entry = stack.top();
                Node* node = entry.node;

                if (entry.direction == kInputDirection) {
                    if (entry.input != node->input_edges().end()) {
                        Edge edge = *entry.input;
                        Node* input = edge.to();
                        ++(entry.input);
                        if (NodeProperties::IsControlEdge(edge)) {
                            // Visit next control input.
                            if (!Participates(input))
                                continue;
                            if (GetData(input)->visited)
                                continue;
                            if (GetData(input)->on_stack) {
                                // Found backedge if input is on stack.
                                if (input != entry.parent_node) {
                                    VisitBackedge(node, input, kInputDirection);
                                }
                            } else {
                                // Push input onto stack.
                                DFSPush(stack, input, node, kInputDirection);
                                VisitPre(input);
                            }
                        }
                        continue;
                    }
                    if (entry.use != node->use_edges().end()) {
                        // Switch direction to uses.
                        entry.direction = kUseDirection;
                        VisitMid(node, kInputDirection);
                        continue;
                    }
                }

                if (entry.direction == kUseDirection) {
                    if (entry.use != node->use_edges().end()) {
                        Edge edge = *entry.use;
                        Node* use = edge.from();
                        ++(entry.use);
                        if (NodeProperties::IsControlEdge(edge)) {
                            // Visit next control use.
                            if (!Participates(use))
                                continue;
                            if (GetData(use)->visited)
                                continue;
                            if (GetData(use)->on_stack) {
                                // Found backedge if use is on stack.
                                if (use != entry.parent_node) {
                                    VisitBackedge(node, use, kUseDirection);
                                }
                            } else {
                                // Push use onto stack.
                                DFSPush(stack, use, node, kUseDirection);
                                VisitPre(use);
                            }
                        }
                        continue;
                    }
                    if (entry.input != node->input_edges().end()) {
                        // Switch direction to inputs.
                        entry.direction = kInputDirection;
                        VisitMid(node, kUseDirection);
                        continue;
                    }
                }

                // Pop node from stack when done with all inputs and uses.
                DCHECK(entry.input == node->input_edges().end());
                DCHECK(entry.use == node->use_edges().end());
                DFSPop(stack, node);
                VisitPost(node, entry.parent_node, entry.direction);
            }
        }

        void ControlEquivalence::DetermineParticipationEnqueue(ZoneQueue<Node*>& queue,
            Node* node)
        {
            if (!Participates(node)) {
                AllocateData(node);
                queue.push(node);
            }
        }

        void ControlEquivalence::DetermineParticipation(Node* exit)
        {
            ZoneQueue<Node*> queue(zone_);
            DetermineParticipationEnqueue(queue, exit);
            while (!queue.empty()) { // Breadth-first backwards traversal.
                Node* node = queue.front();
                queue.pop();
                int max = NodeProperties::PastControlIndex(node);
                for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
                    DetermineParticipationEnqueue(queue, node->InputAt(i));
                }
            }
        }

        void ControlEquivalence::DFSPush(DFSStack& stack, Node* node, Node* from,
            DFSDirection dir)
        {
            DCHECK(Participates(node));
            DCHECK(!GetData(node)->visited);
            GetData(node)->on_stack = true;
            Node::InputEdges::iterator input = node->input_edges().begin();
            Node::UseEdges::iterator use = node->use_edges().begin();
            stack.push({ dir, input, use, from, node });
        }

        void ControlEquivalence::DFSPop(DFSStack& stack, Node* node)
        {
            DCHECK_EQ(stack.top().node, node);
            GetData(node)->on_stack = false;
            GetData(node)->visited = true;
            stack.pop();
        }

        void ControlEquivalence::BracketListDelete(BracketList& blist, Node* to,
            DFSDirection direction)
        {
            // TODO(mstarzinger): Optimize this to avoid linear search.
            for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) {
                if (i->to == to && i->direction != direction) {
                    TRACE("  BList erased: {%d->%d}\n", i->from->id(), i->to->id());
                    i = blist.erase(i);
                } else {
                    ++i;
                }
            }
        }

        void ControlEquivalence::BracketListTRACE(BracketList& blist)
        {
            if (FLAG_trace_turbo_ceq) {
                TRACE("  BList: ");
                for (Bracket bracket : blist) {
                    TRACE("{%d->%d} ", bracket.from->id(), bracket.to->id());
                }
                TRACE("\n");
            }
        }

#undef TRACE

    } // namespace compiler
} // namespace internal
} // namespace v8
